package main

import "math"

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

// 不太好想，看题解
func distributeCoins(root *TreeNode) int {
	var dfs func(node *TreeNode) int
	step := 0

	dfs = func(node *TreeNode) int {
		if node == nil {
			return 0
		}

		left := dfs(node.Left)
		right := dfs(node.Right)
		// 移动步数
		step = step + int(math.Abs(float64(left))) + int(math.Abs(float64(right)))
		// 当前（多余，可正可负）节点，向上移动
		return left + right + (node.Val) - 1
	}
	dfs(root)
	return step
}
